package LeetCode.tree;

public class LC_572 {  // 时间复杂度O(s * t)
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root != null){
            if(isSameTree(root,subRoot)){
                return true;
            }
            if (isSubtree(root.left, subRoot)){
                return true;
            }
            if (isSubtree(root.right, subRoot)){
                return true;
            }
        }
        return subRoot == null;
    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null) {
            return q == null;
        }
        if(q != null) {
            if(p.val != q.val) {
                return false;
            } else {
                boolean leftTree = isSameTree(p.left,q.left);
                boolean rightTree = isSameTree(p.right,q.right);
                return leftTree && rightTree;
            }
        }
        return false;
    }
}
